{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check Completeness of a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isCompleteTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的完全性检验"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点<meta charset=\"UTF-8\" />&nbsp;<code>root</code> ，请你判断这棵树是否是一棵 <strong>完全二叉树</strong>&nbsp;。</p>\n",
    "\n",
    "<p>在一棵 <strong><a href=\"https://baike.baidu.com/item/完全二叉树/7773232?fr=aladdin\" target=\"_blank\">完全二叉树</a></strong> 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 <code>h</code> 层）中可以包含<meta charset=\"UTF-8\" />&nbsp;<code>1</code>&nbsp;到<meta charset=\"UTF-8\" />&nbsp;<code>2<sup>h</sup></code> 个节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/15/complete-binary-tree-1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5,6]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/15/complete-binary-tree-2.png\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5,null,7]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>值为 7 的节点不满足条件「节点尽可能靠左」。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 100]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-completeness-of-a-binary-tree](https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-completeness-of-a-binary-tree](https://leetcode.cn/problems/check-completeness-of-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6]', '[1,2,3,4,5,null,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = collections.deque([(root, 1)])\n",
    "        heapid = 1\n",
    "        while len(q) > 0:\n",
    "            numnodes = len(q)\n",
    "            for _ in range(numnodes):\n",
    "                (node, nodeid) = q.popleft()\n",
    "                if nodeid != heapid:\n",
    "                    return False\n",
    "                if node.left:\n",
    "                    q.append((node.left, 2*nodeid))\n",
    "                if node.right:\n",
    "                    q.append((node.right, 2*nodeid+1))\n",
    "                heapid += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        nodes = [root]\n",
    "        i = 0\n",
    "        \n",
    "        while nodes[i]:\n",
    "            nodes.append(nodes[i].left)\n",
    "            nodes.append(nodes[i].right)\n",
    "            i += 1\n",
    "            \n",
    "        return not any(nodes[i:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def level_iterate(root, nodes, parent=None, depth=0):\n",
    "\n",
    "    if depth >= len(nodes):\n",
    "        nodes.append([])\n",
    "\n",
    "    if not root:\n",
    "        nodes[depth].append(None)\n",
    "        return\n",
    "\n",
    "    root.parent = parent\n",
    "    nodes[depth].append(root)\n",
    "    level_iterate(root.left, nodes, root, depth+1)\n",
    "    level_iterate(root.right, nodes, root, depth+1)\n",
    "\n",
    "def level_iterate_flatten(root):\n",
    "    r = []\n",
    "    level_iterate(root, r)\n",
    "    nodes = []\n",
    "    for i in range(len(r)):\n",
    "        for j in range(len(r[i])):\n",
    "            nodes.append(r[i][j])\n",
    "    \n",
    "    while nodes[-1] == None:\n",
    "        nodes.pop()\n",
    "    return nodes\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        nodes = level_iterate_flatten(root)\n",
    "        for i in range(1, len(nodes)):\n",
    "            node = nodes[i]\n",
    "            if node == None:\n",
    "                return False\n",
    "            parent = nodes[int((i - 1) / 2)]\n",
    "            if node.parent.val != parent.val:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return True\n",
    "        stack = [root]\n",
    "        path = [root.val]\n",
    "        while stack:\n",
    "            r = stack.pop(0)\n",
    "            if r.left:\n",
    "                stack.append(r.left)\n",
    "                path.append(r.left.val)\n",
    "            else:\n",
    "                path.append(None)\n",
    "            if r.right:\n",
    "                stack.append(r.right)\n",
    "                path.append(r.right.val)\n",
    "            else:\n",
    "                path.append(None)\n",
    "        i = 0\n",
    "        while path[i]:\n",
    "            i += 1\n",
    "        j = len(path) - 1\n",
    "        while not path[j]:\n",
    "            j -= 1\n",
    "        print(path, i ,j)\n",
    "        return i == j + 1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        bfs=[root]\n",
    "        i=0\n",
    "        while bfs[i]:\n",
    "            bfs.append(bfs[i].left)\n",
    "            bfs.append(bfs[i].right)\n",
    "            i+=1\n",
    "        return not any(bfs[i:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return False\n",
    "        que = queue.Queue()\n",
    "        que.put(root)\n",
    "        flag = False\n",
    "        while not que.empty():\n",
    "            cur_node = que.get()\n",
    "            if cur_node.left is not None:\n",
    "                que.put(cur_node.left)\n",
    "            if cur_node.right is not None:\n",
    "                que.put(cur_node.right)\n",
    "            if cur_node.left is None and cur_node.right is not None:\n",
    "                return False\n",
    "            if flag:\n",
    "                if cur_node.left or cur_node.right:\n",
    "                    return False\n",
    "            if not (cur_node.left and cur_node.right):\n",
    "                flag = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        pre=root\n",
    "        queue=[root]\n",
    "        while queue:\n",
    "            node=queue.pop(0)\n",
    "            if node and not pre:\n",
    "                return False\n",
    "            if node:\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            pre=node\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        res = []\n",
    "        flag = False\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            next_stack = []\n",
    "            for node in stack:\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    if flag:\n",
    "                        return False\n",
    "                    next_stack.append(node.left)\n",
    "                else:\n",
    "                    flag=True\n",
    "                if node.right:\n",
    "                    if flag:\n",
    "                        return False\n",
    "                    next_stack.append(node.right)\n",
    "                else:\n",
    "                    flag = True\n",
    "            res += tmp\n",
    "            stack = next_stack\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        L = [(root,1)]\n",
    "        i = 0\n",
    "        while(i< len(L)):\n",
    "            if L[i][0].left:\n",
    "                L.append((L[i][0].left, L[i][1]*2))\n",
    "            if L[i][0].right:\n",
    "                L.append((L[i][0].right, L[i][1]*2+1))\n",
    "            i += 1\n",
    "        if L[-1][1] > len(L):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        cur=[root]\n",
    "        stop=False\n",
    "        \n",
    "        while(cur):\n",
    "            res=[]\n",
    "            for i in cur:\n",
    "                if i.left:  \n",
    "                    if stop:\n",
    "                        return False\n",
    "                    else: \n",
    "                        res.append(i.left)\n",
    "                               \n",
    "                else:\n",
    "                    stop=True\n",
    "                         \n",
    "             \n",
    "                    \n",
    "                if i.right: \n",
    "                    if stop:\n",
    "                        return False\n",
    "                    else:\n",
    "                        res.append(i.right)\n",
    "                        \n",
    "                else:  \n",
    "                    stop=True\n",
    "                    \n",
    "                     \n",
    "            cur=res\n",
    "        return True\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        queue = [root]\n",
    "        prev = root\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not prev and node:\n",
    "                return False\n",
    "            if node:\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            prev = node\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "       nodes = [root]\n",
    "       i = 0\n",
    "       while nodes[i]:\n",
    "           nodes.append(nodes[i].left)\n",
    "           nodes.append(nodes[i].right)\n",
    "           i += 1\n",
    "       return not any(nodes[i:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node:\n",
    "                if not queue:\n",
    "                    queue.append(node.left)\n",
    "                elif not queue[-1] and node.left:\n",
    "                    return False\n",
    "                else:\n",
    "                    queue.append(node.left)\n",
    "                if not queue:\n",
    "                    queue.append(node.right)\n",
    "                elif not queue[-1] and node.right:\n",
    "                    return False\n",
    "                else:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        edge=[root]\n",
    "        has_none=False\n",
    "        while edge:\n",
    "            # print([node.val if node else 'None' for node in edge])\n",
    "            edge2=[]\n",
    "            for node in edge:\n",
    "                if node:\n",
    "                    if has_none:\n",
    "                        return False\n",
    "                    edge2.append(node.left)\n",
    "                    edge2.append(node.right)\n",
    "                else:\n",
    "                    has_none=True\n",
    "            edge=edge2\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        a,m = set(),0\n",
    "        def dfs(r,id):\n",
    "            nonlocal a,m\n",
    "            if r:\n",
    "                a.add(id)\n",
    "                m = max(m,id)\n",
    "                dfs(r.left,2*id)\n",
    "                dfs(r.right,2*id+1)\n",
    "        dfs(root,1)\n",
    "        return len(a)==m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\r\n",
    "        if not root: return True\r\n",
    "        # 层序遍历\r\n",
    "        import copy\r\n",
    "        curLayer = [root]\r\n",
    "        preLayer = [root]\r\n",
    "        num = 1\r\n",
    "        judgeLast = False\r\n",
    "        hasNoneLeaf = False\r\n",
    "        while curLayer:\r\n",
    "\r\n",
    "            if len(curLayer) != num:\r\n",
    "                while preLayer:\r\n",
    "                    checkNode = preLayer.pop(0) \r\n",
    "                    if hasNoneLeaf:\r\n",
    "                        if checkNode.left or checkNode.right:\r\n",
    "                            return False\r\n",
    "                    else:\r\n",
    "                        if not checkNode.left:\r\n",
    "                            hasNoneLeaf = True\r\n",
    "                        if hasNoneLeaf and  checkNode.right:\r\n",
    "                            return False\r\n",
    "                        if not checkNode.right:\r\n",
    "                            hasNoneLeaf = True\r\n",
    "                judgeLast = True        \r\n",
    "\r\n",
    "\r\n",
    "            num *= 2 \r\n",
    "            preLayer = copy.deepcopy(curLayer)\r\n",
    "\r\n",
    "            nextLayer = []\r\n",
    "            while curLayer:\r\n",
    "                cur = curLayer.pop(0)\r\n",
    "                if cur.left:\r\n",
    "                    nextLayer.append(cur.left)\r\n",
    "                if cur.right:\r\n",
    "                    nextLayer.append(cur.right)\r\n",
    "            curLayer = nextLayer\r\n",
    "\r\n",
    "            if judgeLast and nextLayer:\r\n",
    "                return False\r\n",
    "        return True\r\n",
    "            \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: TreeNode) -> bool:\n",
    "        nodes = [(root, 1)]\n",
    "        i = 0 \n",
    "        while i < len(nodes):\n",
    "            node, v = nodes[i]\n",
    "            i += 1\n",
    "            if node:\n",
    "                nodes.append((node.left, 2 * v))\n",
    "                nodes.append((node.right, 2 * v + 1))\n",
    "        return nodes[-1][1] == len(nodes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = [root]\n",
    "        flag = False\n",
    "        while q:\n",
    "            tmp = q.pop(0)\n",
    "            if not tmp:               # 如果当前为空，设置 flag 表示已经遇到空结点了\n",
    "                flag = True\n",
    "                continue\n",
    "            if flag == True:          # 如果当前不为空，且之前有空结点，则必不为完全二叉树\n",
    "                return False\n",
    "            q.append(tmp.left)        # 注意此处不判断左右子结点是否为空，而是直接加入队列\n",
    "            q.append(tmp.right)\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        flag = False\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "\n",
    "        while stack:\n",
    "            tmp = stack.pop(0)\n",
    "            if not tmp:\n",
    "                flag = True\n",
    "                continue\n",
    "            if flag:\n",
    "                return False\n",
    "            stack.append(tmp.left)\n",
    "            stack.append(tmp.right)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isCompleteTree(self, root):\n",
    "        nodes=[(root,1)]\n",
    "        i=0\n",
    "        while i<len(nodes):\n",
    "            node,v=nodes[i]\n",
    "            i+=1\n",
    "            if node:\n",
    "                nodes.append((node.left,2*v))\n",
    "                nodes.append((node.right,2*v+1))\n",
    "        return len(nodes)==nodes[-1][1]\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        nodes = [(root, 1)]\n",
    "        print(nodes)\n",
    "        i = 0\n",
    "        while i < len(nodes):\n",
    "            node, v = nodes[i]\n",
    "            i += 1\n",
    "            if node:\n",
    "                nodes.append((node.left, 2*v))\n",
    "                nodes.append((node.right, 2*v+1))\n",
    "\n",
    "        return  nodes[-1][1] == len(nodes)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        vis = set()\n",
    "        def f(o, val):\n",
    "            if not o:\n",
    "                return\n",
    "            vis.add(val)\n",
    "            f(o.left, val * 2)\n",
    "            f(o.right, val * 2 + 1)\n",
    "        f(root, 1)\n",
    "        return list(range(1, 1 + len(vis))) == sorted(list(vis))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isCompleteTree(self, root: Optional[TreeNode]) -> bool:\n",
    "#         # 层序遍历，只要出现过空节点，就不能再出现任何非空节点\n",
    "#         q = collections.deque([root])\n",
    "#         # 注意：当前层空节点靠右，但下一层还有节点，也是非完全的\n",
    "#         # 所以设置的是全局变量\n",
    "#         none_flag = False  # 是否出现过空节点\n",
    "#         while q:\n",
    "#             for _ in range(len(q)):\n",
    "#                 curr = q.popleft()\n",
    "#                 if curr==None:\n",
    "#                     none_flag = True\n",
    "#                 else: # 当前非空\n",
    "#                     if none_flag: # 又出现非空节点，则是不完全\n",
    "#                         return False\n",
    "#                     q.append(curr.left)\n",
    "#                     q.append(curr.right)\n",
    "#         return True\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def isCompleteTree(self, root):\n",
    "        # 层序，当标号超出总记录长度时停止（即记录空节点后停止）\n",
    "        nodes = [(root, 1)]\n",
    "        i = 0\n",
    "        while i < len(nodes):\n",
    "            node, v = nodes[i]\n",
    "            i += 1\n",
    "            if node:\n",
    "                nodes.append((node.left, 2*v))\n",
    "                nodes.append((node.right, 2*v+1))\n",
    "\n",
    "        return  nodes[-1][1] == len(nodes) # 标号正确，则倒数第二行满，则前n-2行均满\n",
    "\n",
    "# 作者：LeetCode\n",
    "# 链接：https://leetcode.cn/problems/check-completeness-of-a-binary-tree/solutions/18187/er-cha-shu-de-wan-quan-xing-jian-yan-by-leetcode/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        queue = [root]\n",
    "        end = False\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not node:\n",
    "                end = True\n",
    "            else:\n",
    "                if end:\n",
    "                    return False\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "  def isCompleteTree(self, root: Optional[TreeNode]) -> bool:\n",
    "    q = [(root, 0)]\n",
    "    lv = -1\n",
    "    t = False\n",
    "    while len(q) > 0:\n",
    "      n, l = q.pop(0)\n",
    "      if None == n.right and None == n.left:\n",
    "        t = True\n",
    "      elif n.right != None and n.left == None:\n",
    "        return False\n",
    "      else:\n",
    "        if n.left != None:\n",
    "          if l == lv or t:\n",
    "            return False\n",
    "          else:\n",
    "            q.append((n.left, l + 1))\n",
    "        if n.right != None:\n",
    "          if l == lv or t:\n",
    "            return False\n",
    "          else:\n",
    "            q.append((n.right, l + 1))\n",
    "        elif -1 == lv:\n",
    "          lv = l + 1\n",
    "          t = True\n",
    "      # print(f\"lv {lv} t{t} @{n.val}\")\n",
    "    return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
